package com.zyf;

import java.util.Scanner;

/**
 * 9 只出现一次的数字

给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次,找出那个只出现一次的元素

说明 : 你可以不使用额外空间来实现吗?

示例 1 
输入 :  {2,2,1}
输出 :  1
示例 2 
输入 :  {4,1,2,1,2}
输出 :  4

 * @author lenovo
 * @Date 2020年7月2日
 * @Time 下午4:33:16
 */
public class _09_onlyFirstNumber {

	public static void main(String[] args) {
		@SuppressWarnings("resource")
		Scanner sc = new Scanner(System.in);
		System.out.println("输入一个数组长度 : " );
		int n = sc.nextInt();
		int[] arr1 = new int[n];
		System.out.println("输入一个长度为 " + n +"的数组 : " );
		for (int i = 0; i < arr1.length; i++) {
			arr1[i] = sc.nextInt();
		}
		int m = onlyFirstNumber(arr1);
		System.out.println("只出现一次的数字为 : " + m);
	}
	/**
	 * 只出现一次的数字方法
	 * @param arr1
	 * @return 出现一次的数字
	 * 
	 * 思路:
	 * 异或!!!!!
	 * 能想到就很简单,把数组中的全部元素依次异或
	 * 比如:4,1,2,1,2
	 *  4 ^ 1 ^ 2 ^ 1 ^ 2 = 4
	 * 因为自己和自己异或始终是0,最后就只剩下了那个出现了一次的元素
	 * 
	 * 题目要求不使用额外空间,使用方法实参 arr1[0] 也就是第一个元素保存数据
	 */
	public static int onlyFirstNumber(int[] arr1) {
		//依次异或嘛!
		for (int i = 1; i < arr1.length; i++) {
			arr1[0] = arr1[0] ^ arr1[i];
		}
		return arr1[0];
	}

}
